package 中等.动态规划.子序列;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元
 * 素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 */
public class 最长递增子序列_300 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 4, 3, -1};
        System.out.println(lengthOfLIS2(nums));

    }

    /**
     * 动态规划
     * 1，定义子问题
     * 以i结尾的递增子序列，最大长度是多少
     * 2，状态转移方程
     * 之前的数加上第i个数是否可以构成递增子序列
     * a，假如存在pre<i&&nums[pre]<nums[i] ，那么dp[i]=dp[pre]+1
     * 由于可能存在多个pre符号条件，需要找到最大的dp[pre]
     * b，假如不存在符号条件的pre，那么dp[i]=1，意味着以i开头以i结尾
     * 另外：并不是以最后一个结尾的递增子序列就一定是最大的！！！
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int ans = 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);  //以i结尾的最小长度为1
        for (int cur = 1; cur < nums.length; cur++) {
            for (int pre = 0; pre < cur; pre++) {
                if (nums[pre] < nums[cur]) {
                    dp[cur] = Math.max(dp[cur], dp[pre] + 1);
                }
            }
            ans = Math.max(ans, dp[cur]);  //避免最后需要遍历一遍，维护最大长度
        }
        return ans;
    }

    /**
     * 贪心+二分
     * 要想要获取尽可能长严格递增序列，那么上升的越慢，就会越长
     * 例如 1 2 4 3 -1
     * 定义 dp[i] 表示长度为 i+1 的递增序列 末尾元素的值
     * dp[0] = 1  表示长度为 1 的递增序列 末尾元素是 1
     * dp[1] = 2  如果 curVal > dp中已经赋值的所有元素，说明最长递增序列，增加 1 个长度
     * dp[2] = 4
     * 遍历到 3 时 ，二分从数组中找到 >= 3 的第一个数是 4 那么将
     * dp[2] = 3，代表长度为 3 的最长递增序列的末尾元素是 3
     * 遍历到 -1 时
     * dp[0] = -1，说明长度为 1 的最长字段序列末尾元素是 -1
     * 最后得出
     * dp[] = {-1,2,3} 最长为 3
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length];
        // dp的 dpMaxIdx+1 就是长度，记录nums遍历到i的最长长度为 rightIdx+1
        int dpMaxIdx = 0;
        dp[0] = nums[0];
        for (int numIdx = 1; numIdx < nums.length; numIdx++) {
            int left = 0, right = dpMaxIdx;
            int target = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] >= nums[numIdx]) {
                    target = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 如果dp中没有二分找到 >= curNum 的值，那么最长长度 +1
            if (target == -1) {
                dpMaxIdx++;
                target = dpMaxIdx;
            }
            dp[target] = nums[numIdx];
        }
        return dpMaxIdx + 1;
    }

}
